package com.aqie.easy.trie;



/**
 * 720. 词典中最长的单词
 * todo
 */
public class LongestWord {
    String longestword = "";
    int longlen = 0;
    public String longestWord(String[] words) {
        Trie trie = new Trie();

        //依次插入string
        for(String word: words){
            trie.insert(word);
        }

        for (String word : words){
            if (trie.isBuild(word) && word.length() > longlen){
                longestword = word;
                longlen = word.length();
            }else if(trie.isBuild(word) && word.length() == longlen){     //当出现一样长的字符串时，进行比较
                char[] longestchar = longestword.toCharArray();
                char[] wordchar = word.toCharArray();
                for(int i=0; i<longlen; i++){
                    if(wordchar[i]-longestchar[i] < 0){
                        longestword = word;
                        break;
                    }else if(wordchar[i]-longestchar[i] > 0) break;
                }
            }

        }
        return longestword;

    }

    public class Trie {
        TrieNode root = new TrieNode('/');

        //用来插入一个string
        public void insert(String string){
            char[] c = string.toCharArray();
            TrieNode p = root;
            for(int i=0; i<c.length; i++){
                int index = c[i] - 'a';
                if(p.next[index] == null){
                    TrieNode trienode = new TrieNode(c[i]);
                    p.next[index] = trienode;
                }
                p = p.next[index];
            }
            p.isword = true;
        }

        //用来判断这个字符串是不是由其他节点依次加一个字符组成
        public boolean isBuild(String string){
            char[] c = string.toCharArray();
            TrieNode p = root;
            for(int i=0; i<c.length; i++){
                if(!p.next[c[i]-'a'].isword) return false;
                p = p.next[c[i]-'a'];
            }
            return true;
        }

    }

    public class TrieNode {
        public char data;
        public boolean isword = false;
        public TrieNode[] next = new TrieNode[26];
        public TrieNode(char c){
            data = c;
        }

    }

    public static void main(String[] args) {
        String[] words = {"w","wo","wor","worl", "world"};
        LongestWord longestWord = new LongestWord();
        String s = longestWord.longestWord(words);
        System.out.println(s);
    }

}
